#pragma once
#include <stdio.h>

typedef struct NodeData 
{
	int mValue;
	int compare(NodeData* p) {
		if (p) {
			return mValue > p->mValue ? 1 : mValue == p->mValue ? 0 : -1;
		}
		return -2;
	}

} *pNodeData;

typedef struct TreeNode
{
	TreeNode* parent;
	TreeNode* left;
	TreeNode* right;
	int h;
	int bf;
	pNodeData m_pData;
} *pTreeNode;

class AVLTree
{
	pTreeNode mRoot;
	void left_rotate(pTreeNode pivot);
	void right_rotate(pTreeNode pivot);
	void left_right_rotate(pTreeNode pivot);
	void right_left_rotate(pTreeNode pivot);
	
	bool bin_insert(pTreeNode root, pTreeNode node);
	void adjust_tree(pTreeNode leaf);
	void calBalanceFactor(pTreeNode node);
	void calHeight(pTreeNode node);

public:
	AVLTree(void);
	~AVLTree(void);

	void insert(pNodeData node);
	void deleteData(pNodeData pData);
	pTreeNode search(pNodeData pData);

	friend bool checkAVLTree(AVLTree& tree);
};
